%************************************************************************************************
%**    Autor: Maik Funkat																					**
%**																													**
%**    Dieses Dokument steht unter der folgenden Lizenz:									**
%**    Namensnennung-NichtKommerziell-KeineBearbeitung 2.0 Deutschland    	**
%**    			(http://creativecommons.org/licenses/by-nc-nd/2.0/de/)					**
%**																													**
%************************************************************************************************
\documentclass[12pt,a4paper]{scrreprt}

%weitere Packages einbinden
%\usepackage{amsmath}
%\usepackage{amssymb}
%\usepackage{amsthm}
%\usepackage{fancyhdr}
%\usepackage{gastex}
\usepackage[utf8x]{inputenc}
\usepackage{lmodern}
%\usepackage{mathtools}
\usepackage{ngerman}
%\usepackage{ogonek}					%für das Ogonek unter polnischen Namen
%\usepackage{pstricks}


%Layout einstellen
\pagestyle{empty}
%\fancyhead[LCR]{}
%\renewcommand{\headrulewidth}{0pt}
\setlength{\parindent}{0cm}


% Abkürzungen für Funktionen	
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\val}{\mathrm{val}}
\newcommand{\peek}{\mathrm{peek}}
\newcommand{\pop}{\mathrm{pop}}
\newcommand{\push}{\mathrm{push}}
\newcommand{\tree}{\mathrm{tree}}
\newcommand{\pre}{\mathrm{pre}}
\newcommand{\lab}{\mathrm{label}}
\newcommand{\bl}{\beta_\textsf{L}}
\newcommand{\br}{\beta_\textsf{R}}
\newcommand{\childsize}[1]{|#1|}

% Abkürzungen für Mengen
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Y}{\mathbb{Y}}
\newcommand{\T}{\mathcal{T}}
\newcommand{\dom}{\mathrm{dom}} 


%Abkürzungen für Pfeile
\newcommand{\ra}{\ensuremath{\rightarrow}}
\newcommand{\Ra}{\ensuremath{\Rightarrow}}

	
%Abkürzung für Text und Zeichensymbole
\newcommand{\minus}{\mathbin\backslash}	%	Mengen-Minus
\newcommand{\dcup}{\mathbin{\dot\cup}}	%	disjunkte Vereinigung
\newcommand{\veps}{\varepsilon}


%Abkürzungen für Textformatierung
\newcommand{\todo}[1]{\footnote{\textbf{ToDo}: #1}}


%Wortsilben
\hyphenation{Teil-ableitungs-baum}
\hyphenation{Ab-leitungs-baum}

%==================================================================================%

\begin{document}
\

\vspace{17mm}

{\textsc{\fontsize{50pt}{80}\selectfont Programm-}}

\

{\textsc{\fontsize{50pt}{80}\selectfont\hspace{2cm}dokumentation}}
\newpage

\tableofcontents

\chapter{Allgemeines}
Sämtliche Dateien sind online in einem SVN-Repository verfügbar unter 
\begin{center}	
{\texttt{https://code.google.com/p/traversal-wt/}}
\end{center}
Alle Programme sind in Java 7 implementiert wurden und befinden sich in einem Alphastatus. Das heißt sie wurden nicht auf Ausführungszeit und Speicherplatzverbrauch optimiert. Auch werden nicht alle unsinnigen Eingaben abgefangen. Die verwendeten Begriffe werden in der Diplomarbeit definiert und erklärt.

Die Quellcodes stehen unter 
\begin{center}
\texttt{http://code.google.com/p/traversal-wt/source/browse/}
\end{center}
im Unterordner \emph{src} zur Verfügung. Im Unterordner \emph{tests} befinden sich ein paar Testbeispiele für Wort- und Baumgrammatiken. Im Unterordner \emph{tex} befinden sich die Diplomarbeit und diese Programmdokumentation.


\chapter{Programme}
Alle Programme wurden als Jar-Archive gepackt. Sie sind unter der Adresse
\begin{center}
\texttt{http://code.google.com/p/traversal-wt/downloads/list}
\end{center}
zu finden und nachfolgend aufgelistet. Sie können in der Konsole mittels \emph{java -jar [Programmname]} aufgerufen werden.

\section{Wortgrammatiken}
\subsection{rePair}
Ein Recursive-Pairing-Algorithmus wurde in der Klasse \textsc{mf.words.grammar.rePair} implementiert. Aufgerufen wird sie über
\begin{center}
	rePair \emph{filename} [\emph{output}] [\emph{debug}]
\end{center}
wobei \emph{filename} ein Pfad zu der zu komprimierenden Datei ist. Es wird im selben Ordner eine Straight-Line-Wortgrammatik \emph{filename.jPair} erstellt. Optional kann mit \emph{output} der Ausgabedatei geändert werden. Mit dem Schalter \emph{debug} werden während der Berechnung zusätzliche Informationen auf der Konsole ausgegeben.

\subsection{wordTraverse}
Eine komplette Traversierung der Straight-Line-Wortgrammatik kann mit der Klasse \textsc{mf.words.traversal.wordTraverse} durchgeführt werden. Dazu ist einfach per Kommandozeile
\begin{center}
wordTraverse \emph{filename} [\emph{direction}] [\emph{debug}]
\end{center}
einzugeben und die durch \emph{filename} definierte Grammatik wird dekomprimiert ausgegeben. Optional kann mit \emph{direction} gewählt werden ob der Text von links nach rechts (direction = 0), von rechts nach links (direction = 1) oder in beide Richtungen ausgegeben werden soll (direction = 2). Mit dem Schalter \emph{debug} werden wieder während der Berechnung zusätzliche Informationen auf der Konsole ausgegeben.

\subsection{wordNavigate}
Die Klasse \textsc{mf.words.navigation.wordNavigate} ist ein einfaches Programm mit einer grafischen Oberfläche auf der die Navigation durch den Text ausgegeben wird. Sie wird mit 
\begin{center}
wordNavigate [\emph{debug}]
\end{center}
gestartet. Haben wir eine Grammatik-Datei ausgewählt, so können wir mit den Pfeiltasten nach links und rechts im Text navigieren. Haben wir den Anfang bzw.\, das Ende des Textes erreicht, so wird dies angezeigt. Im Menü können wir mit dem Menüpunkt "`Open"' eine neue Straight-Line-Baumgrammatik öffnen ohne das Programm neustarten zu müssen. Der Menüpunkt "`Quit"' beendet das Programm. Der Schalter \emph{debug} ist optional und gibt, sofern gesetzt, im Fenster die Größe der Grammatik und den aktuellen Stack aus.

\section{Baumgrammatiken}
Zur Navigation in Bäumen gibt es drei Versionen.

\subsection{treeNavigate mit binären Symbolen und Konstanten}
Mit dem Aufruf
\begin{center}
treeNavigateBinary [\emph{debug}]
\end{center}
wird das Programm zur Navigation in Bäumen gestartet. Es ist nur für Straight-Line-Baumgrammatiken über einem Rangalphabet mit binären Symbolen und Konstanten. Der Schalter \emph{debug} gibt im Fenster den aktuellen Stack sowie die aktuelle Regel aus.

\subsection{treeNavigate mit beliebigen Rängen}
Der Aufruf
\begin{center}
treeNavigateAll [\emph{debug}]
\end{center}
unterscheidet sich vom vorherigen Programm darin, dass hier beliebige Ränge bei Nichtterminale erlaubt sind. Der Schalter \emph{debug} verhält sich gleich.

\subsection{treeNavigate mit Preorder-Nummer}
Mit dem Aufruf
\begin{center}
treeNavigateAll [\emph{debug}]
\end{center}
erhalten wir neben Nichtterminalen beliebigen Ranges auch noch die Preorder-Nummer der Knoten. Der Schalter \emph{debug} verhält sich gleich.

\section{Beispiele}
Für Wortgrammatiken können mit der \emph{rePair}-Klasse eigene Beispiele erstellt werden. Für Straight-Line-Baumgrammatiken sind die Regeln zeilenweise anzugeben als kommagetrennte Liste.
Die Nichtterminale sind dabei von $0$ beginnend (dies ist auch das Startsymbol) nummeriert. Die Regel für das $i$-te Nichtterminal steht dann in Zeile $i+1$. Terminalsymbole können beliebig gewählt werden. Den Parameter $x$ geben wir auch als $x$ an. Für Typ-1-Regeln $A \ra B(C)$ hat nun die Zeile die Form $B,C$, für $A(x) \ra B(C(x))$ hat sie die Form $A,B,x$. Für Typ-2-Regeln $A \ra a$ hat sie die Form $a$, für $A(x) \ra f(B_1, \ldots, B_{i-1}, x, B_{i+1}, \ldots, B_n)$ hat sie die Form $f,B_1,\ldots,B_{i-1},x,B_{i+1},\ldots,B_n$.

So stehen die Zeilen
\begin{verbatim}
1,2
3,3,x
3,5
4,6,x
f,x,5
a
f,5,x
\end{verbatim}

für die Straight-Line-Baumgrammatik mit den Regeln
\[
\begin{array}{lll}
	A_0 \ra A_1(A_2)			&	A_1(x) \ra A_3(A_3(x))	&	A_2 \ra A_3(A_5)	\\
	A_3(x) \ra A_4(A_6(x))	&	A_4(x) \ra f(x, A_5)		&	A_5 \ra a \\
	A_6(x) \ra f(A_5, x)
\end{array}
\]

\end{document}